package Java1Test;

import utils.PrintArr;

public class testquicksort {
    public static void main(String[] args) {
        int[] nums = {5, 2, 3, 1};
        sortArray(nums);
        PrintArr.printArr(nums);
    }

    public static int[] sortArray(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return nums;
        }
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    public static void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }

        int start = left;
        int end = right;
        int baseNumber = nums[left];

        while (start < end) {
            // 从右向左找第一个小于基准数的元素
            while (start < end && nums[end] >= baseNumber) {
                end--;
            }
            // 从左向右找第一个大于基准数的元素
            while (start < end && nums[start] <= baseNumber) {
                start++;
            }

            if (start < end) {
                swap(nums, start, end);
            }
        }

        // 将基准数放到正确位置
        swap(nums, left, start);

        // 递归处理左右子数组
        quickSort(nums, left, start - 1);
        quickSort(nums, start + 1, right);
    }

    public static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}